#include<iostream>
#include<string>
#include<vector>
#include<stack>
//https://leetcode.cn/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/
using namespace std;

class Node {
public:
    int val;
    Node* left;
    Node* right;

    Node() {}

    Node(int _val) {
        val = _val;
        left = NULL;
        right = NULL;
    }

    Node(int _val, Node* _left, Node* _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};

class Solution {
public:

    Node* InorderBuid(Node*& prev, Node* cur)
    {
        if (cur == NULL)
        {
            return NULL;
        }

        InorderBuid(prev, cur->left);

        cur->left = prev;

        if (prev)
            prev->right = cur;

        prev = cur;
        InorderBuid(prev, cur->right);
        return NULL;
    }

    Node* treeToDoublyList(Node* root)
    {
        if (!root)
            return NULL;
        Node* prev = NULL;
        InorderBuid(prev, root);
        Node* head, * tail;
        head = tail = root;
        while (head->left)
        {
            head = head->left;
        }

        while (tail->right)
        {
            tail = tail->right;
        }

        head->left = tail;
        tail->right = head;
        return head;
    }
};